package leetcode.other.greedy;

import java.util.Arrays;

/**
 * @Description: https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/
 * 有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组points，
 * 其中points[i] = [xstart, xend]表示水平直径在xstart和xend之间的气球。
 * 你不知道气球的确切 y 坐标。
 *
 * 一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。
 * 在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend，
 * 且满足  xstart≤ x ≤ xend，则该气球会被 引爆。
 * 可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
 *
 * 给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数。
 *
 * @Author Ammar
 * @Create 2023/7/5 10:06
 */
public class _452_用最少数量的箭引爆气球 {
    public int findMinArrowShots(int[][] points) {
        int[][] newPoints = new int[points.length][2];
        for (int i = 0; i < points.length; i++) {
            newPoints[i][0] = points[i][0];
            newPoints[i][1] = points[i][1];
        }

        Arrays.sort(newPoints, (int[] o1, int[] o2) -> Integer.compare(o1[0], o2[0]));

        int count = 1;
        for (int i = 1; i < newPoints.length; i++) {
            // 如果下一个气球的左边界大于上一个气球的右边界，说明需要一支新的箭
            if (newPoints[i][0] > newPoints[i - 1][1]) {
                count++;
            } else {
                // 更新一起的球的右边界的最小值
                newPoints[i][1] = Math.min(newPoints[i][1], newPoints[i - 1][1]);
            }
        }
        return count;
    }
}
